package com.yc.algorithm.leetcode;

/**
 * You are climbing a staircase. It takes n steps to reach the top.
 *
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/climbing-stairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ClimbingStairs {

    public static void main(String[] args) {
        ClimbingStairs climbingStairs = new ClimbingStairs();
        System.out.println(climbingStairs.climbStairsOne(5));
        System.out.println(climbingStairs.climbStairsOnePlus(5));
        System.out.println(climbingStairs.climbStairsTwo(5));
        System.out.println(climbingStairs.climbStairsThree(5));
    }

    // 递归调用完成
    public int climbStairsOne(int n) {
        if (n < 0 || n > 45) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return climbStairsOne(n - 1) + climbStairsOne(n - 2);
    }

    // 优化递归实现
    public int climbStairsOnePlus(int n) {
        int[] store = new int[n+1];
        return climbStairsOnePlusSup(n, store);
    }

    private int climbStairsOnePlusSup(int n, int[] store){

        if (store[n] > 0) {
            return store[n];
        }
        if (n == 1) {
            store[n] = 1;
        } else if (n == 2) {
            store[n] = 2;
        } else {
            store[n] = climbStairsOnePlusSup(n-1, store) + climbStairsOnePlusSup(n-2, store);
        }
        return store[n];

    }




    // 动态规划实现
    public int climbStairsTwo(int n) {
        if (n == 1) {
            return n;
        }
        // 定义需要动态规划的数组
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i=3; i<=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    // ,,,
    public int climbStairsThree(int n) {
        double sqrt = Math.sqrt(5);
        double result = (Math.pow((1+sqrt)/2, n+1)-Math.pow((1-sqrt)/2, n+1))/sqrt;
        return (int) result;
    }
}
